class Solution
{
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>> &redEdges, vector<vector<int>> &blueEdges)
    {
        vector<vector<int>> redAdjTable(n);
        vector<vector<int>> blueAdjTable(n);
        for (auto &redEdge : redEdges)
        {
            redAdjTable[redEdge[0]].push_back(redEdge[1]);
        }
        for (auto &blueEdge : blueEdges)
        {
            blueAdjTable[blueEdge[0]].push_back(blueEdge[1]);
        }

        vector<int> answer(n, INT_MAX);

        auto bfs = [&](bool colorFlag)
        {
            vector<bool> redVisited(n, false);
            vector<bool> blueVisited(n, false);
            queue<int> q;
            q.push(0);
            if (colorFlag)
            {
                redVisited[0] = true;
            }
            else
            {
                blueVisited[0] = true;
            }
            int step = 0;
            while (!q.empty())
            {
                int qSize = q.size();
                for (int i = 0; i < qSize; ++i)
                {
                    int node = q.front();
                    q.pop();
                    answer[node] = min(answer[node], step);
                    if (colorFlag)
                    {
                        for (int adjNode : blueAdjTable[node])
                        {
                            if (!blueVisited[adjNode])
                            {
                                blueVisited[adjNode] = true;
                                q.push(adjNode);
                            }
                        }
                    }
                    else
                    {
                        for (int adjNode : redAdjTable[node])
                        {
                            if (!redVisited[adjNode])
                            {
                                redVisited[adjNode] = true;
                                q.push(adjNode);
                            }
                        }
                    }
                }
                colorFlag = !colorFlag;
                ++step;
            }
        };

        constexpr bool BlueFirst = true;
        constexpr bool RedFirst = false;
        bfs(BlueFirst);
        bfs(RedFirst);

        for (int &ans : answer)
        {
            if (ans == INT_MAX)
            {
                ans = -1;
            }
        }

        return answer;
    }
};